/*
 * Copyright 2010 Joshua Smith and Nelson Llewellyn
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */
package norse.util;

import java.util.Arrays;

/**
 * Class that represents a range of IP addresses. Immutable.
 */
public final class IPv4Range
{

    /**
     * Constructor.
     *
     * @param _startAddr start address. Must be 4-element array.
     * @param _endAddr end address. Must be 4-element array. Must be equal to or
     *      after the start address.
     *
     * @throws IllegalArgumentException if parameters are invalid
     */
    public IPv4Range(int[] _startAddr, int[] _endAddr)
            throws IllegalArgumentException
    {
        //Make defensive coppies
        try
        {
            startAddr = Arrays.copyOf(_startAddr, _startAddr.length);
            endAddr = Arrays.copyOf(_endAddr, _endAddr.length);
        }
        catch (NullPointerException npe)
        {
            throw new IllegalArgumentException(
                    "Start and end adress must be non-null.");
        }

        assertAddressIsValid(startAddr);
        assertAddressIsValid(endAddr);

        //If the end address is before the beginning address
        if(compareAddresses(endAddr, startAddr) == ComparisonResult.BEFORE)
        {
            throw new IllegalArgumentException(
                    "End address must be after or equal to start address.");
        }
    }

    /**
     * Getter.
     *
     * @return the range's start address.
     */
    public int[] getStartAddr()
    {
        return Arrays.copyOf(startAddr, startAddr.length);
    }

    /**
     * Getter.
     *
     * @return the range's end address.
     */
    public int[] getEndAddr()
    {
        return Arrays.copyOf(endAddr, endAddr.length);
    }

    //NOTE: We have to represent addresses as int arrays, since the morons at
    //      Sun... erm... Oracle still won't give us unsigned variables.
    //      However, this means that we have to manually range check the
    //      variables. (This is another reason that this class is immutable!)
    /** The start address of this IP range */
    private final int[] startAddr;
    /** The end address of this IP range */
    private final int[] endAddr;

    /**
     * Finds the union of this range and the provided range.
     *
     * <p/>Creates a new range that is the union of this range and the range
     * provided as a parameter. (i.e. Merges the two ranges.)
     *
     * @param _addressToMerge the range to merge with this range. Must return
     *      true when compared with the {@code canBeMergedWith} method, or
     *      an exception will occur.
     *
     * @return a new range that is the union of the two ranges.
     *
     * @throws IllegalArgumentException if the ranges do not overlap at all,
     *      or if the parameter is null
     *
     * @see IPv4Range#overlapsWithRange(norse.util.IPv4Range) overlapsWithRange
     */
    public IPv4Range rangeUnion(IPv4Range _addressToMerge)
            throws IllegalArgumentException
    {
        if (_addressToMerge == null)
        {
            throw new IllegalArgumentException(
                    "Address to merge with must be non-null");
        }
        
        if(!overlapsWithRange(_addressToMerge))
        {
            throw new IllegalArgumentException("A union cannot be performed on "
                    + "ranges that do not overlap.");
        }

        int[] paramStartAddr = _addressToMerge.getStartAddr();
        int[] paramEndAddr = _addressToMerge.getEndAddr();

        int[] newStartAddr = Arrays.copyOf(startAddr, startAddr.length);
        int[] newEndAddr = Arrays.copyOf(endAddr, endAddr.length);

        if(compareAddresses(paramStartAddr, startAddr)
                == ComparisonResult.BEFORE)
        {
            newStartAddr = paramStartAddr;
        }

        if(compareAddresses(paramEndAddr, endAddr)
                == ComparisonResult.AFTER)
        {
            newEndAddr = paramEndAddr;
        }

        return new IPv4Range(newStartAddr, newEndAddr);
    }

    /**
     * Find the complement of the provided range in this range.
     *
     * <p/>Creates new range(s) that don't include the addresses in the
     * parameter.
     *
     * @param _complementAddress the range to remove from this range
     *
     * @return an array of new ranges. Array wil have between 0 and 2 entries
     * (inclusive).
     *
     * @throws IllegalArgumentException if the ranges do not overlap at all,
     *      or if the parameter is null
     *
     * @see IPv4Range#overlapsWithRange(norse.util.IPv4Range) overlapsWithRange
     */
    public IPv4Range[] rangeComplement(IPv4Range _complementAddress)
            throws IllegalArgumentException
    {
        if (_complementAddress == null)
        {
            throw new IllegalArgumentException(
                    "Address to merge with must be non-null");
        }

        if (!overlapsWithRange(_complementAddress))
        {
            throw new IllegalArgumentException("A union cannot be performed on "
                    + "ranges that do not overlap.");
        }

        int[] paramStartAddr = _complementAddress.getStartAddr();
        int[] paramEndAddr = _complementAddress.getEndAddr();

        ComparisonResult startAddrComp = compareAddresses(
                paramStartAddr, startAddr);
        ComparisonResult endAddrComp = compareAddresses(
                paramEndAddr, endAddr);

        //If the parameter range completely encoses this range
        if ( (startAddrComp == ComparisonResult.BEFORE
                || startAddrComp == ComparisonResult.EQUAL)
                && (endAddrComp == ComparisonResult.AFTER
                || endAddrComp == ComparisonResult.EQUAL))
        {
            //Return zero-length array, rather than null. (Effective Java)
            return new IPv4Range[0];
        }
        //If the parameter range is at the beginning of this range
        else if (startAddrComp == ComparisonResult.BEFORE
                || startAddrComp == ComparisonResult.EQUAL)
        {
            IPv4Range [] returnVal = new IPv4Range[1];

            //We want to start at the address AFTER the parameter's end
            incrementAddress(paramEndAddr);

            returnVal[0] = new IPv4Range(paramEndAddr, endAddr);
            return returnVal;
        }
        //If the parameter range is at the end of this range
        else if (endAddrComp == ComparisonResult.AFTER
                || endAddrComp == ComparisonResult.EQUAL)
        {
            IPv4Range [] returnVal = new IPv4Range[1];

            //We want to end at the address BEFORE the parameter's end
            decrementAddress(paramStartAddr);

            returnVal[0] = new IPv4Range(startAddr, paramStartAddr);
            return returnVal;
        }
        //If the parameter range is contained within this range
        else
        {
            IPv4Range [] returnVal = new IPv4Range[2];

            //We want to end at the address BEFORE the parameter's end
            decrementAddress(paramStartAddr);

            //We want to start at the address AFTER the parameter's end
            incrementAddress(paramEndAddr);


            returnVal[0] = new IPv4Range(startAddr, paramStartAddr);

            returnVal[1] = new IPv4Range(paramEndAddr, endAddr);
            return returnVal;
        }
    }

    /**
     * Determines if this IP range can be merged with another IP range.
     *
     * @param _comparisonVal the IP range to compare against to determine
     *      mergability.
     *
     * @return {@code true} if mergable; {@code false} otherwise.
     *
     * @throws IllegalArgumentException if {@code _comparisonVal} is
     * {@code null}.
     */
    public boolean overlapsWithRange(IPv4Range _comparisonVal)
            throws IllegalArgumentException
    {
        if(_comparisonVal == null)
        {
            throw new IllegalArgumentException(
                    "Comparison value cannot be null");
        }

        //If the comparison value terminates before or after this range
        if(compareAddresses(_comparisonVal.endAddr, startAddr)
                == ComparisonResult.BEFORE
                || compareAddresses(_comparisonVal.startAddr, endAddr)
                == ComparisonResult.AFTER)
        {
            return false;
        }

//        //If any of the addresses are the same, a merge can happen
//        if(Arrays.equals(_comparisonVal.startAddr, startAddr)
//                || Arrays.equals(_comparisonVal.endAddr, endAddr)
//                || Arrays.equals(_comparisonVal.startAddr, endAddr)
//                || Arrays.equals(_comparisonVal.endAddr, startAddr))
//        {
//            return true;
//        }
//
//        //If the comparison value is before the current range, with some overlap
//        if(compareAddresses(_comparisonVal.endAddr, startAddr)
//                == ComparisonResult.AFTER
//                && compareAddresses(_comparisonVal.startAddr, startAddr)
//                == ComparisonResult.BEFORE)
//        {
//            return true;
//        }
//
//        //If the comparison value is after the current range, with some overlap
//        if(compareAddresses(_comparisonVal.startAddr, endAddr)
//                == ComparisonResult.BEFORE
//                && compareAddresses(_comparisonVal.endAddr, endAddr)
//                == ComparisonResult.AFTER)
//        {
//            return true;
//        }
//
//        //If the address is a subset of the current range
//        if(compareAddresses(_comparisonVal.startAddr, startAddr)
//                == ComparisonResult.AFTER
//                && compareAddresses(_comparisonVal.endAddr, endAddr)
//                == ComparisonResult.BEFORE)
//        {
//            return true;
//        }

        return true;
    }

    /**
     * Compare two addresses.
     *
     * <p/>This method's functionality can be read as:
     * "{@code _comparisonVal} is {@code [Return Value]} (e.g. "less than")
     * {@code _referenceVal}"
     *
     * @param _comparisonVal the address to compare with.
     * @param _referenceVal the address to compare against.
     *
     * @return a {@code ComparisonResult}
     *
     * @throws IllegalArgumentException if either parameter is invalid
     *
     * @see IPv4Range#assertAddressIsValid(int[]) Assert validity
     */
    public static ComparisonResult compareAddresses(int[] _comparisonVal,
            int[] _referenceVal) throws IllegalArgumentException
    {
        assertAddressIsValid(_comparisonVal);
        assertAddressIsValid(_referenceVal);

        return uncheckedCompareAddresses(_comparisonVal, _referenceVal);
    }

    /**
     * Unchecked version of the {@code compareAddresses} method.
     *
     * <p/>This private method doesn't check its parameters for validity. This
     * should save significant time for methods that have already validated
     * their parameters.
     *
     *
     * @param _comparisonVal the address to compare with.
     * @param _referenceVal the address to compare against.
     *
     * @return a {@code ComparisonResult}
     */
    private static ComparisonResult uncheckedCompareAddresses(
            int[] _comparisonVal, int[] _referenceVal)
            throws IllegalArgumentException
    {
        for(int i = 0; i < 4; ++i)
        {
            if(_comparisonVal[i] < _referenceVal[i])
            {
                return ComparisonResult.BEFORE;
            }
            else if(_comparisonVal[i] > _referenceVal[i])
            {
                return ComparisonResult.AFTER;
            }
        }

        return ComparisonResult.EQUAL;
    }

    /**
     * Assert that an address is valid
     *
     * @param _address the address to validate. Should be a non-null array with
     *      four elements. For each octet "x", the following must be true:
     *      {@code 0 <= x <= 255}.
     *
     * @throws IllegalArgumentException if the address doesn't validate.
     */
    public static void assertAddressIsValid(int[] _address)
            throws IllegalArgumentException
    {
        if(_address == null)
        {
            throw new IllegalArgumentException("Address cannot be null.");
        }

        if(_address.length != 4)
        {
            throw new IllegalArgumentException("Adress must contain 4 bytes.");
        }

        for(int currAddr : _address)
        {
            if(currAddr < 0)
            {
                throw new IllegalArgumentException(
                        "IP address octets cannot be less than zero.");
            }
            else if(currAddr > 255)
            {
                throw new IllegalArgumentException(
                        "IP address octets cannot be greater than 255.");
            }
        }
    }

    /**
     * Increment an address, with octet rollover.
     *
     * @param _address the address to increment
     * 
     * @throws IllegalArgumentException if the address isn't valid, or if the
     *      address cannot be incremented (255.255.255.255, for example).
     */
    public static void incrementAddress(int []_address)
            throws IllegalArgumentException
    {
        //Increment the last octet
        ++_address[3];

        //Handle rollover
        int currOctet = 3;
        while(_address[currOctet] > 255 && currOctet > 0)
        {
            --_address[currOctet];
            ++_address[currOctet - 1];
            
            --currOctet;
        }

        //If we've rolled over all the octets and it's still invalid, then we
        //have an error!
        if (currOctet == 0 && _address[currOctet] > 255)
        {
            --_address[currOctet];
            throw new IllegalArgumentException("Address "
                    + Arrays.toString(_address) + " cannot be incremented");
        }
    }

    /**
     * Decrement an address, with octet rollover.
     *
     * @param _address the address to decrement
     *
     * @throws IllegalArgumentException if the address isn't valid, or if the
     *      address cannot be decremented (0.0.0.0, for example).
     */
    public static void decrementAddress(int []_address)
            throws IllegalArgumentException
    {
        //Decrement the last octet
        --_address[3];

        //Handle rollover
        int currOctet = 3;
        while(_address[currOctet] < 0 && currOctet > 0)
        {
            ++_address[currOctet];
            --_address[currOctet - 1];

            --currOctet;
        }

        //If we've rolled over all the octets and it's still invalid, then we
        //have an error!
        if (currOctet == 0 && _address[currOctet] < 0)
        {
            --_address[currOctet];
            throw new IllegalArgumentException("Address "
                    + Arrays.toString(_address) + " cannot be decremented");
        }
    }
}
